# icectf-2016 - attack of the hellman
# https://github.com/grocid/CTF/tree/master/IceCTF/2016#attack-of-the-hellman-200-p
# vuln was that b was small

p=0x113b7d158a909efadc7216ca15fd51c419eb41ab108e0aa1d45da70c78185593d44bdb402476181c008ef36bc5378b0ad4c868ca4ed4f754c3c1b1f0891bcd8ad7d3db07251de90f4362cb5895f836eec8851d3fe3d68083db8a63053ec4078a55df017f1d43393f3aa2a453bb334417671731731e1e7687c77d104ff76aed523b6980831a4c4b55d74c4de77462d9a596ce7fcb3090d0abb8f94989c1b3701e533ebd722c855fba9ff17d64ce9b3306841157ee49b1c1fb3a38c93b9faaa84efcfdceba923b73b8682835ca322a1350bcc322d7eb34259d8302f55157c2c5d72c8aebb7b57f9f08809ee034258cf2e3c8e0982a155b72fdc79432eceb83b49d9
g=0xa9074b6e6d5bba3d024b90eeaee1f5b969fee32c5c25b91698755450509a8beb4100b046c9c6601981e208bc6e505aa67fdd224eff829a8cd8ebc1267c2cb4192b18ab1bcf5dba908e2cd849be038b5d52d5cf836eed63ee54fab1838a7152361a298bbeab3cc2d6f2b84097622fa5493dca99b4b6a648dcc886b607a8dc9590d995cf2e1f24ac5f277a2260d34410dc3b832ed6dc4928e92dfa8a807ddbdf77574d7bb34a45ca08bb7c8b89aa1fd1380abcbd75f99d3e819da9617356b650f9cc21ccffe913b09ca547967bb12feedbdb97730ccff09cc63aab6f6fc7b33392211da29bf32538b38a514cad4ea271e97618e39b0ab7cb152499093b7afbae2f
A=0x18776a5cf81fc30572aa9682dfb2f7d606e8073de536853dd9be8a391261dcca6cebea2a2b1337f2a057d238152729cea6983a8ef2b111d8096f212db771229830e2e6d4839a37355d4efb265183f199cd573fa99a38183e7ee3cc7fdac7c92078b6c1535b142965379f1c7e73d5a95725dfb75749529a687bf9b7e01a0b4511a05d96999608c2527a0308f2360d26706233d451f62edc8f2e76fde85c631b601d12a828657efe65aba78fccd46d79a84bc3380da71fad6472d9e666fd99fbd7c154555501b608d4cef875099e037eef3712a5e3108f95c1e01b2a8f0961569c77738a459b65b0ac39109b30ab3226d7b92a1db080a99bbb86f6e96266b13df7
B=0xbecd8332380e8c0f3969602e4924473ade119dad5fe6f2d9582dc8196ae85dfa80fab3c001f8bea1ca6c63b9f8f264742beaede2bd11c86bf4d6a0fa7df1dd84da318a7142f2228dbb8dd37a5a3c5a772dd2c744184a41743f4286ba2ccfa431c1571cd63a9ee1bb398b4dd09ccaa426b37f72f4452c2f37a96634e8d6604362e2836891818e9744f00323ade93e10aa1785cc1865fff57ec5caacf74b11ebed16384613145a2e33141a9523252b952cf0eb9c33914d067b66a2a03133f044f336efee054eec905dfa14af970f556b44c52e3814e0914a2393bb56da5aca7b88c45fcaf02f76fc9718746c15901b8ea86801f0b07eca7385dd1cb6991e65e421

table = {}
S = 0

print '[-] Generating table...'

for b in range(0, 2**33, 2**20): # sufficient bounds
    table[pow(g, b, p)] = b

print '[-] Performing look-up in table...'

for i in range(0, 2**18):
    print 'i: %d' % i
    B = (B * g) % p
    if B in table:
        b = table[B] - i
        print  ' >> B = g ^', b
        S = pow(A, b, p)
        break

#import base36
#print '[+] Key found:\n\n', base36.dumps(S), '\n'
